P1453 城市环路 - 洛谷

城市环路

题目描述

一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。

B 市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕 B 市的环路，环路之内便是 B 市中心。

整个城市可以看做一个 $n$ 个点， $n$ 条边的单圈图（保证图连通），唯一的环便是绕城的环路。保证环上任意两点有且只有 $2$ 条简单路径互通。图中的其它部分皆隶属城市郊区。

现在，有一位名叫 Jim 的同学想在 B 市开店，但是任意一条边的 $2$ 个点不能同时开店，每个点都有一定的人流量，第 $i$ 个点的人流量是 $p_{i}$ ，在该点开店的利润就等于 $p_{i} \times k$ ，其中 $k$ 是一个常数。

Jim 想尽量多的赚取利润，请问他应该在哪些地方开店？

输入格式

$\begin{aligned} n \\ a_{1} & a_{2} & \dots & a_{n} \\ u_{1} & v_{1} \\ u_{2} & v_{2} \\ ⋮ \\ u_{n} & v_{n} \\ k \end{aligned}$
第一行一个整数 $n$ ，代表城市中点的个数。城市中的 $n$ 个点由 $0 \sim n - 1$ 编号。
第二行有 $n$ 个整数，第 $(i + 1)$ 个整数表示第 $i$ 个点的人流量 $p_{i}$ 。
接下来 $n$ 行，每行有两个整数 $u, v$ ，代表存在一条连接 $u$ 和 $v$ 的道路。
最后一行有一个实数，代表常数 $k$ 。
(点从 0 开始)
数据范围：
$1 \leq n \leq 10^{5}$ ， $1 \leq p_{i} \leq 10^{4}$ ， $0 \leq u, v < n$ ， $0 \leq k \leq 10^{4}$ ， $max {p r e c i s i o n () i s 6}$ .

输出格式

输出一行一个实数代表答案，结果保留一位小数。

样例 #1

样例输入 #1

样例输出 #1

12.0